package edu.whu.rose.clock.ssql.subgraph;

import java.io.File;
import java.io.FileWriter;
import java.io.IOException;
import java.util.Date;

import edu.whu.rose.clock.kps.graph.GraphMatrix;
import edu.whu.rose.clock.ssql.graph.RRadiusSubGraph;
import edu.whu.rose.clock.ssql.util.MyMath;
import edu.whu.rose.clock.ssql.util.SequentialIntArray;

public class SubgraphExtractor {

	private int radius;
	
	private int empiricalFactor1 = 10;
	private int empiricalFactor2 = 100;
	private double upperBound;
	private double lowerBound;
	private double neighborBound;
	
	private GraphMatrix graph;
	private int order;

	private SubgraphDB sgdb;
	private SubgraphCache cache;
	
	private int overNeighborBound;
	private int overUpperBound;
	private int overLowerBound;
	
	public SubgraphExtractor(int radius, int order, String dbEnv) {
		this.radius = radius;
		this.order = order;
		this.graph = new GraphMatrix(order);
		this.sgdb = new SubgraphDB(dbEnv);
	}
	
	public static void main(String[] args) {
		File file = new File("dbEnv_subgraph");
		if (file.isDirectory()) {
			File[] files = file.listFiles();
			for (int i = 0; i < files.length; i++) {
				files[i].delete();
			}
		}
		
		SubgraphExtractor gm = new SubgraphExtractor(2, 198467, "dbEnv_subgraph");
		gm.loadMatrix("F:/data/5000029_graph/edge.txt");
//		SubgraphExtractor gm = new SubgraphExtractor(2, 11012, "dbEnv_subgraph2");
//		gm.loadMatrix("graph/edge.txt");
		gm.init(100000);
		gm.genMaxSubGraphs();
		gm.genSubGraphInvertedList();
		
//		System.out.println("start printing...");
//		gm.printAllSubGraphs("subgraphs.txt");
//		gm.printInvertedList("invlist.txt");
		
//		System.out.println("Total number of edges: " + gm.getEdgeNumber());
		
		gm.close();
		System.out.println("Finished");
		
	}
	
	public void init(int capacity) {
		if (!this.sgdb.initEnv() || !this.sgdb.openDB()) {
			System.exit(1);
		}
		
		computeBounds();
		
		this.cache = new SubgraphCache(graph, capacity, sgdb, radius);
	}
	
	public void close() {
		this.sgdb.closeDB();
	}
	
	public void loadMatrix(String edgeFile) {
		this.graph.loadEdges(edgeFile);
	}
	
	private void computeBounds() {
		double degree = 2d * graph.getM() / graph.getN();
		upperBound = 1;
		lowerBound = 1;
		for (int i = 0; i < radius; i++) {
			upperBound += Math.pow(empiricalFactor1 * degree, i + 1);
			lowerBound += Math.pow(degree, i + 1);
		}
		neighborBound = 1 + empiricalFactor2 * degree;
		System.out.println("UpperBound: " + upperBound);
		System.out.println("LowerBound: " + lowerBound);
		System.out.println("neighborBound: " + neighborBound);
	}
	
	public void genMaxSubGraphs() {
		Date start = new Date();
		int[][] neighbors = new int[graph.getN()][];
		for (int i = 0; i < graph.getN(); i++) {
			RRadiusSubGraph rrsg = extractSubgraph(i + 1, neighbors);
//			if (i % 1000 == 0)
//				System.out.println("generate a raw subgraph " + (i + 1));
			if (rrsg != null) {
				this.addMaxSubGraph(rrsg);
			}
		}
		Date end = new Date();
		System.out.println("Time exhausted: " + (end.getTime() - start.getTime()) + " ms");
		cache.reprocess_flush_indexing();
		this.cache.statistic();
		System.out.println("Neighbor Bound: " + neighborBound);
		System.out.println("Number of over-neighbor-bound: " + overNeighborBound);
		System.out.println("Upper Bound: " + upperBound);
		System.out.println("Number of over-upper-bound: " + overUpperBound);
		System.out.println("Lower Bound: " + lowerBound);
		System.out.println("Number of over-lower-bound: " + overLowerBound);
	}
	
	public RRadiusSubGraph extractSubgraph(int source, int[][] neighbors) {
		if (radius < 1) {
			return null;
		}
		
		SequentialIntArray vertexes = new SequentialIntArray();
		SequentialIntArray sphere = new SequentialIntArray();
		int[] temp = neighbors[source - 1];
		if (temp == null) {
			temp = graph.genNeighbors(source);
			neighbors[source - 1] = temp;
		}
		for (int i = 0; i < temp.length; i++) {
			if (temp[i] != source) {
				vertexes.insert(temp[i]);
				sphere.insert(temp[i]);
			}
		}
		
		for (int i = 1; i < radius; i++) {
			SequentialIntArray newSphere = new SequentialIntArray();
			for (int j = 0; j < sphere.getCapacity(); j++) {
				int[] temp2 = neighbors[sphere.get(j) - 1];
				if (temp2 == null) {
					temp2 = graph.genNeighbors(sphere.get(j));
					neighbors[sphere.get(j) - 1] = temp2;
				}
				if (temp2.length > neighborBound) {
//					System.out.println(sphere.get(j) + " large number of neighbor: " + temp2.length);
					overNeighborBound++;
					continue;
				}
				if (vertexes.getCapacity() + newSphere.getCapacity() + temp2.length >= upperBound) {
					overUpperBound++;
					return new VaryingRadiusSubgraph(source, i, vertexes.getArray());
				}
				for (int k = 0; k < temp2.length; k++) {
					if (vertexes.binarySearch(temp2[k]) == -1) {
						newSphere.insert(temp2[k]);
					}
				}
			}
			sphere = newSphere;
			for (int j = 0; j < newSphere.getCapacity(); j++) {
				vertexes.insert(newSphere.get(j));
			}
		}
		
		if (vertexes.getCapacity() < lowerBound) {
			overLowerBound++;
		}
		
		return new VaryingRadiusSubgraph(source, radius, vertexes.getArray());
	}

	private void addMaxSubGraph(RRadiusSubGraph rrsg) {
		int row = rrsg.getRow();
		int[] vertexes = rrsg.getVertexes();
		int result = 0;
		boolean select = true;
		
		for (int i = 0; i < vertexes.length; i++) {
			int compRow = vertexes[i];
			if (compRow < row) {
				RRadiusSubGraph comp = cache.get(compRow);
				if (comp != null) {
					int[] compVertexes = comp.getVertexes();
					result = MyMath.compareIntArrays(vertexes, compVertexes);
					if (result == MyMath.ARR1_CONTAIN_ARR2) {
						cache.delete(compRow, true);
					}
					else if (result == MyMath.ARR2_CONTAIN_ARR1) {
						select = false;
						break;
					}
				}
			}
			else {
				break;
			}
			
		}
		
		if (select) {
			cache.insert(rrsg);
		}
		else {
			cache.delete(row, false);
		}
	}
	
	public void genSubGraphInvertedList() {
		this.sgdb.genSubGraphInvertedList(order);
	}
	
	public int getEdgeNumber() {
		return graph.getM();
	}
	
	public void printAllSubGraphs(String file) {
		try {
			FileWriter fw = new FileWriter(file);
			this.printAllSubGraphs(fw);
		}
		catch (IOException ex) {
			ex.printStackTrace();
		}
	}
	
	public void printAllSubGraphs(FileWriter fw) {
		try {
			this.sgdb.printSubGraphs(fw);
			
			fw.close();
		}
		catch (IOException ex) {
			ex.printStackTrace();
		}
	}
	
	public void printInvertedList(String file) {
		try {
			FileWriter fw = new FileWriter(file);
			this.printInvertedList(fw);
		}
		catch (IOException ex) {
			ex.printStackTrace();
		}
	}
	
	public void printInvertedList(FileWriter fw) {
		try {
			this.sgdb.printInvList(fw);
			
			fw.close();
		}
		catch (IOException ex) {
			ex.printStackTrace();
		}
	}

}
